home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / near.m < prev    next >
Encoding:
Text File  |  1992-01-14  |  6.7 KB  |  238 lines
  1.  
  2. #include <stdlib.h>
  3. #ifdef MYDIR
  4. #else
  5. #include "TwoDView.h"
  6. #include "TwoDTSP.h"
  7. #include <appkit/graphics.h>
  8. #endif
  9. #include <math.h>
  10. #include <limits.h>
  11. #include <stdio.h>
  12. #include "tspheaders.h"
  13. #include "prototypes.h"
  14.  
  15. /************************************************************************/
  16. /* This function implements the Nearest Neighbor Algorithm for the
  17.    Travelling Salesperson Algorithm.  It provides an approximate optimal
  18.    value rather than the optimal value. 
  19.  
  20.    Reference: Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem, 
  21.              1985, Wiley and Sons, p 150.
  22. */
  23. /************************************************************************/
  24. /* Parameters:   TwoDView *self: Ye Old Drawing Object
  25.  
  26.                     float *Data: Pointer to the list of points.
  27.                                  Used to draw intermediate graph.
  28.  
  29.                 float *Distance: Pointer to area that contains the
  30.                                  Distances Between Each Pair of Cities
  31.  
  32.                       int *Tour: Pointer to area that will contain the
  33.                                  indices of the n arcs that are selected 
  34.                                  to be a part of the tour
  35.  
  36.              int NumberOfCities: Number of cities in the problem
  37. */
  38. /************************************************************************/
  39. /************************************************************************/
  40. #ifdef MYDIR
  41. float NearestNeighbor(float *Distance,int *Tour,int NumberOfCities) {
  42. #else
  43. float NearestNeighbor(TwoDView *self,float *data,float *Distance,int *Tour,
  44.                         int NumberOfCities) {
  45. #endif
  46. int i,j,k,x,y,I,J,From,To,FirstCity,LastCity,MthCity,SubTourEnd,NewCity;
  47. int *OnTour;
  48. float ThisDistance,NewDistance,OptimalValue;
  49. char msg[256];
  50.  
  51. /* allocate space for OnTour */
  52. OnTour = (int *)malloc(NumberOfCities*sizeof(int));
  53. if (OnTour == (int *) 0)
  54.   printf("Malloc for OnTour failed. \n");
  55.  for (i=0;i<NumberOfCities;i++) {
  56.    OnTour[i] = 0;
  57.  }
  58.  
  59. #ifdef DEBUGMYDIR
  60. for (i=0;i<(NumberOfCities-1)*NumberOfCities/2;i++) {
  61.   printf("Distance[%d] = %f; \n",i,Distance[i]);
  62. }
  63. #endif
  64.  
  65. /* find the two cities with the minimum distance */
  66. ThisDistance = ClosestCities(Distance,&From,&To,NumberOfCities);
  67.  
  68. /* if ThisDistance doesn't change, there is a problem ... */
  69. if (ThisDistance == INT_MAX) {
  70.   printf("Error no initial subtour found. \n");
  71. }
  72. #ifdef DEBUGMYDIR
  73. else {
  74.   printf("initial subtour \n");
  75.   printf("from %d to %d distance %f \n",From,To,ThisDistance);
  76. }
  77. #else
  78. sprintf(msg,"from %d to %d distance %f \n",From,To,ThisDistance);
  79. STATUS(msg);
  80. #endif
  81.  
  82. /* given a subtour of m cities, add city m+1 closest to the mth city. */
  83.  
  84. /* OnTour indicates status of city 
  85.    1 -- city is on tour 
  86.    0 -- city is not yet on the tour */
  87.  
  88. Tour[0]  = From;
  89. Tour[1]  = To;
  90. OnTour[From] = OnTour[To] = 1;
  91.  
  92. FirstCity = From;
  93. MthCity = To;
  94. OptimalValue = ThisDistance;
  95. SubTourEnd = 0;
  96.  
  97. NewDistance = INT_MAX; 
  98. NewCity = NumberOfCities;
  99.  
  100. /* keep adding cities until you include all NumberOfCities of them */
  101. while (SubTourEnd < NumberOfCities-2) {
  102.  
  103. #ifdef DEBUGMYDIR
  104.   printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
  105.   printf("MthCity is %d \n",MthCity);
  106. #else
  107. sprintf(msg,"%d cities in tour",SubTourEnd+1);
  108. STATUS(msg);
  109. #endif
  110.  
  111.   /* look at all arcs starting at From */
  112.   I = ArcIndex(MthCity,NumberOfCities);
  113.   J = ArcIndex((MthCity+1),NumberOfCities);
  114.   for (i=I;i<J;i++) {
  115.     /* j = terminating end of this arc */
  116.     j = i-I+MthCity+1;
  117.     /* if the city at the other end isn't already on the tour ...*/
  118.     if (!OnTour[j]) {
  119.       /* Is the arc a new candidate for insertion? */
  120.       k = kfrom(MthCity,j,NumberOfCities);
  121.       ThisDistance = Distance[k];
  122.       if (ThisDistance < 0) {
  123.         printf("Error: ThisDistance = %f for MthCity %f j %f \n",MthCity,j);
  124.       }
  125.       if (ThisDistance < NewDistance) {
  126. #ifdef DEBUGMYDIR
  127.         printf("Changing new city from %d to %d \n",NewCity,j);    
  128.     printf("MthCity, j, %d %d \n",MthCity,j);
  129. #else
  130.     sprintf(msg,"from %d to %d distance %f \n",From,To,ThisDistance);
  131.     STATUS(msg);
  132. #endif
  133.     NewDistance = ThisDistance;
  134.     NewCity = j;
  135.       } 
  136.     }
  137.   }
  138.  
  139.   /* look at all arcs ending at MthCity */
  140.   for (i=0;i<MthCity;i++) {
  141.     /* if the starting city isn't already on the tour ...*/
  142.     if (!OnTour[i]) {
  143.       /* Is this arc a new candidate for insertion? */
  144.       k = kfrom(i,MthCity,NumberOfCities);
  145.       ThisDistance = Distance[k];
  146.       if (ThisDistance < 0) {
  147.         printf("Error: ThisDistance = %f for MthCity %f  i %f \n",MthCity,i);
  148.       }
  149.       if (ThisDistance < NewDistance) {
  150. #ifdef DEBUGMYDIR
  151.         printf("Changing cities from %d to %d \n",NewCity,i);   
  152.     printf("MthCity, i,  %d %d \n",MthCity,i);
  153. #else
  154.     sprintf(msg,"Changing cities from %d to %d \n",NewCity,i);
  155.     STATUS(msg);
  156. #endif
  157.  
  158.     NewDistance = ThisDistance;
  159.     NewCity = i;
  160.       }
  161.     }
  162.   }
  163.  
  164.   if (NewCity >= NumberOfCities) {
  165.     printf("Error: new city has not been found for tour. \n");
  166.     SubTourEnd = NumberOfCities;
  167.     OptimalValue = -1;
  168.   }
  169.   else {
  170.     /* add the new arc going from MthCity to NewCity to Tour */
  171. #ifdef DEBUGMYDIR
  172.     printf("adding arc from %d to %d \n",MthCity,NewCity);
  173. #endif
  174.     SubTourEnd+=1;
  175.     Tour[2*SubTourEnd] = MthCity;
  176.     Tour[2*SubTourEnd+1] = NewCity;
  177.     OnTour[NewCity] = 1;
  178.  
  179.     /* update the Optimal Value */  
  180.     OptimalValue+=NewDistance;
  181.  
  182. #ifdef DEBUGMYDIR
  183.       printf("adding %f to Opval to get %f \n",NewDistance,OptimalValue);
  184. #else
  185.     sprintf(msg,"adding %f to Opval to get %f \n",NewDistance,OptimalValue);
  186.     STATUS(msg);
  187. #endif
  188.  
  189.     /* get ready to start at the top of the list again */
  190.     LastCity = NewCity;
  191.     MthCity = NewCity;
  192.     NewDistance = INT_MAX; 
  193.     NewCity = NumberOfCities; 
  194.  
  195. #ifdef DEBUGMYDIR
  196.     /* print out current subtour */
  197.     for (i=0;i<2*(SubTourEnd+1);i++) {
  198.       printf("i tour %d %d \n",i,Tour[i]);
  199.     }
  200. #endif
  201. #ifdef MYDIR
  202. #else
  203.     /* draw the intermediate tour */
  204.     PSnewinstance();
  205.     for(i=0;i<2*(SubTourEnd+1);i+=2) { 
  206.       x = Tour[i];
  207.       y = Tour[i+1];
  208.      [self drawEdge:X(x):Y(x):X(y):Y(y)];
  209.     }
  210.     NXPing();
  211.     [self->optimalValueField setFloatValue: OptimalValue at: 0];
  212.     usleep(self->drawTime);
  213. #endif
  214.   }
  215. }
  216.  
  217. /* add the final arc going from the first city to the last city */
  218. SubTourEnd+=1;
  219. Tour[2*SubTourEnd] = LastCity;
  220. Tour[2*SubTourEnd+1] = FirstCity;
  221. k = kfrom(FirstCity,LastCity,NumberOfCities);
  222.  
  223. #ifdef DEBUGMYDIR
  224.       printf("adding %f to Opval to get %f \n",Distance[k],OptimalValue);
  225. #else
  226.     sprintf(msg,"adding %f to Opval to get %f \n",NewDistance,OptimalValue);
  227.     STATUS(msg);
  228. #endif
  229. OptimalValue = OptimalValue + Distance[k];
  230. [self->optimalValueField setFloatValue: OptimalValue at: 0];
  231. /* clean up */
  232. free(OnTour);
  233.  
  234. /* return the optimal value */
  235. return(OptimalValue);
  236. }
  237.         
  238.